package day0309

func wordBreak(s string, wordDict []string) bool {
	set := make(map[string]bool)
	for i := 0; i < len(wordDict); i++ {
		set[wordDict[i]] = true
	}
	return help(s, set, 0)
}

func help(s string, set map[string]bool, index int) bool {
	if index == len(s) {
		return true
	}
	for i := index + 1; i <= len(s); i++ {
		if set[s[index:i]] {
			if help(s, set, i) {
				return true
			}
		}
	}
	return false
}
